package arithmetic.demo21;

/**
 * 动态规划： 转化为01背包+ 正难则反：分割等和子集
 */
class Solution {
    public boolean canPartition(int[] nums) {
        // 转化成 01 背包问题
        int len = nums.length;

        // 计算总和
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        // 特殊情况判断一下
        if(sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;

        // 创建dp
        int[][] dp = new int[len+1][target + 1];

        // 初始化
        for(int j = 1 ; j <= target ; j++) {
            dp[0][j] = -1;
        }

        // 从上往下填表
        for(int i = 1 ; i <= len; i++) {
            for(int j = 1; j <= target; j++) {
                // 先继承前面的总和
                dp[i][j] = dp[i-1][j];
                // 注意下标映射
                int index = j -nums[i-1];
                // 从上一层累加上来
                if(index >= 0 && dp[i-1][index] != -1) {
                    dp[i][j] =  dp[i-1][index] + nums[i-1];
                }
            }
            if(dp[i][target] != -1) {
                return true;
            }
        }

        return false;

    }
}

/**
 *
 *  动态规划：布尔dp +  转化为01背包+ 正难则反：分割等和子集
 *
 */

class Solution1 {
    public boolean canPartition(int[] nums) {
        // 转化成 01 背包问题 +  优化版本
        int len = nums.length;

        // 计算总和
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        // 特殊情况判断一下
        if(sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;

        // 创建dp
        boolean[] dp = new boolean[target + 1];

        // 初始化
        dp[0] = true;


        // 从上往下填表
        for(int i = 1 ; i <= len; i++) {
            for(int j = target; j >= nums[i-1]; j--) {

                // 注意下标映射
                int index = j -nums[i-1];
                // 从上一层累加上来
                if( dp[index] ) {
                    dp[j] =  true ;
                }
            }
            //    如果达到了 target 并且合法就直接返回 true
            //    if(dp[target] != -1) {
            //         return true;
            //    }
        }

        return dp[target];

    }
}